package code;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.Stack;


public class PalindromePartitioning {
	
	
	public int[] manacher(String s){
		StringBuilder sb=new StringBuilder();
		int len=s.length();
		int i;
		for(i=0;i<len;i++){
			sb.append("#");
			sb.append(s.charAt(i));
		}
		sb.append("#");
		int n=2*len+1;
		int[] p=new int[n];
		int mx=0;
		int index=0;
		for(i=1;i<n;i++){
			if(mx>i)
				p[i]=p[2*index-i]>mx-i?mx-i:p[2*index-i];
			else
				p[i]=1;
			for(;i-p[i]>=0 && i+p[i]<n;p[i]++)
				if(sb.charAt(i-p[i])!=sb.charAt(i+p[i]))
					break;
			if(mx<i+p[i]){
				mx=i+p[i];
				index=i;
			}
			System.out.println(p[i]);
		}
		return p;
	}
	
	public List<List<String>> partition(String s){
		int n=s.length();
		if(n==0)	return null;
		int[] p=manacher(s);
		int i,j;
		ArrayList<ArrayList<Integer>> vv=new ArrayList<ArrayList<Integer>>(n+1);
		
		for(i=0;i<n;i++){
			vv.add(new ArrayList<Integer>());
			for(j=0;j<=i;j++){
				if(p[i+j+1]>i-j+1){
					vv.get(i).add(j-1);
				}
			}
		}
		
		for(i=0;i<vv.size();i++){
			for(j=0;j<vv.get(i).size();j++)
				System.out.print(vv.get(i).get(j)+" ");
			System.out.println();
		}
		dfsTraverse(s,n-1,vv);
		
		return ans;
	}
	 
	 private List<List<String>> ans=new ArrayList<List<String>>();
	 private Stack<Integer> stack=new Stack<Integer>();
	 
	 public void dfsTraverse(String s,int v,ArrayList<ArrayList<Integer>> vv){
		 if(v==-1){
			 List<Integer> list=new ArrayList<Integer>();
			 while(!stack.empty()){
				 list.add(stack.peek());
				 stack.pop();
			 }
			 for(int i=list.size()-1;i>=0;i--){
				 stack.push(list.get(i));
			 }
			 System.out.print("---- > ");
			 int k=0;
			 List<String> slice=new ArrayList<String>();
			 
			 for(int i=0;i<list.size();i++){
				 System.out.print(s.substring(k,list.get(i)+1)+"  ");
				 slice.add(s.substring(k,list.get(i)+1));
				 k=list.get(i)+1;
			 }
			 System.out.println();
			 ans.add(slice);
			 System.out.println("\n");
			 return ;
		 }
		 stack.push(v);
		 for(int i=0;i<vv.get(v).size();i++){
			dfsTraverse(s,vv.get(v).get(i), vv);
		 }
		 stack.pop();
	 }
	 
	 
	public static void main(String[] args){
		PalindromePartitioning pp=new PalindromePartitioning();
		String s="aab";
//		pp.manacher(s);
		pp.partition(s);
	}
}
